The present invention relates to public key cryptography techniques. It relates more particularly to methods of certifying cryptographic keys.
The fundamental object used to provide confidence in the public part of a cryptographic key (public key) is the certificate. The certificate standard used in numerous networks including the Internet is X.509, version 3. A specification of this is provided by the PKIX working group of the IETF (“Internet Engineering Task Force”) in Request for Comments (RFC) 3280, “Internet X.509. Public Key Infrastructure; Certificate and Certificate Revocation List (CRL) Profile”, published in April 2002. The certificate is an object which comprises, in particular:                the public key to be certified;        the identity of its holder;        a period of validity;        a cryptographic signature of these data by the private key of a Certification Authority (abbreviated to CA) issuing the certificate.        
Having confidence in the public key associated with an identity is equivalent to being certain of the validity of the certificate. For PKIX, a certificate is valid at a given instant T (in terms of confidence):                either if it is expressly declared to be a “certificate of confidence”. In practice, users' certificates are never declared to be certificates of confidence. Instead, a smaller number of certificates of confidence is declared, consisting of the certificates of certain CAs;        or if the following conditions are fulfilled:                    the cryptographic signature of the certificate is mathematically valid;            the instant T forms part of the period of validity of the certificate;            the certificate is not revoked at the instant T;            the public key of the issuing CA is available via a certificate of the CA, and this certificate of the CA is itself valid at the instant T.                        
A certificate is revoked at an instant TR of its period of validity if, from this instant onwards, the CA which has issued it has doubts as to whether the private key associated with the certificate has been compromised. The purpose is to invalidate the certificate from TR onwards. In practice, this is the case when the user of the certificate loses his private key associated with the certified public key or has had it stolen, when the CA no longer wishes to certify the user's key (for example when an employee leaves a business), or in other cases.
According to PKIX, a revoked certificate must be entered in a revocation list (CRL, “Certificate Revocation List”) which is a list of certificates issued by a CA and revoked by it. In theory, a CA must never remove a certificate from a CRL. For example, if a signature is issued at an instant T with a certificate revoked at T, it must always be possible to establish that the certificate was actually revoked at T and therefore that the signature is invalid.
At present, there are two means of establishing that a given certificate has not been revoked:                accessing the CRL. The verifier of the certificate downloads the CRL from a server, verifies the signature of the CRL and then searches for the certificate to be verified in the CRL;        on-line checking of non-revocation. So that the verifier can avoid downloading CRLs which may be very large, an on-line protocol has been specified for checking only one or a few certificates. This is the OCSP protocol described in RFC 2560, “Internet X.509 Public Key Infrastructure; Online Certificate Status Protocol—OCSP”, published in June 1999 by the IETF. According to this protocol, the verifier of the certificate sends an OCSP request to an OCSP server subordinate to the issuing CA, receives the signed OCSP response from this server, verifies the signature of the OCSP response and analyses this response.        
The OCSP is used on-line. The CRLs are used either on-line or off-line, but with regular updating of the CRLs.
In a public key infrastructure, when a certificate expires, the Certification Authority uses a renewal mechanism to deliver a new certificate to the user without having to repeat the registration phase, which consists in the collection and verification of the data relating to the user.
Certificates in the X.509 format are produced for purposes expressed explicitly, called “key usage” (for example, electronic signature, encryption, authentication, time-stamping, SSL server, etc.). A certificate can have a composite key usage. However, in order to limit the risks if a certificate becomes compromised, it is prudent and common practice to assign only a restricted number of these key usages to a single certificate. Thus a user can, in certain cases, have a plurality of certificates, each corresponding to a different use. The problem is then, on the one hand, the user's difficulties in handling these certificates, and, on the other hand, the high management cost for the certification authority. It is therefore useful to be able to distribute these certificates with a restricted key usage, which is as small as possible for each user, without restricting the applications which this makes available to the user.
Public key cryptographic mechanisms can be used to provide a plurality of services having different characteristics, which justify different treatments of the certificates used for the provision of each of the services.
Examples of these services are:
                Confidentiality (encryption): encrypted data must be recoverable if the private key is lost, otherwise they may be irretrievably lost. Encryption keys are therefore sequestered and recoverable.        Electronic signature: the signature key must exist in the form of a single copy, held by the certificate holder, in order to ensure that no-one else has been able to sign in his name. Since the key cannot be duplicated, it cannot be sequestered, and must be different from the encryption key. Signatures must be verifiable beyond the period of validity of the certificate, and therefore the certificate must be retained in order to permit these verifications.        Authentication: the authentication key must also be unique, and therefore different from the encryption key. But the possibility of inducing a user to apply an electronic signature by making him believe that he is simply providing an authentication must be prevented. This could be achieved by replacing the challenge used in a challenge/response public key authentication system. There is a risk that such a message could be signed by the user without his knowledge. The authentication key must therefore be distinguished from the signature key. Furthermore, the authentication certificate does not generally have to be kept beyond its lifetime, since it is only used in unique, instantaneous, and non-persistent verification operations.        
It is therefore frequently necessary to provide specialized certificates, and a user wishing to use a plurality of the above services has to have the same number of certificates. Encryption certificates have a lifetime determined in the Certification Policy of the Certification Authority that issues them. This lifetime is typically from one to three years for users' certificates.
Since this is a long time, it is necessary to allow for the possibility that the certified key may be compromised during the period of validity of the certificate. A revocation and revocation check mechanism is therefore established for invalidating a certificate which must no longer be used. On the other hand, the fact that an electronic signature has been applied with a certificate having a relatively long lifetime gives little information as to the date on which the signature was applied. The electronic signature mechanism must therefore be linked to a time-stamping mechanism.
The electronic signature function makes it possible to guarantee the authenticity of a document, in other words to reliably authenticate its signatory or signatories and to guarantee that the document has not been modified (integrity). The electronic signature is frequently used to guarantee non-repudiation. The non-repudiation of a document is a matter of providing a defence against subsequent denial by its originator.
The most commonly used formats for signed messages are:                PKCS#7, published by RSA Security, Inc., and by the IETF in March 1998 (RFC 2315, “PKCS#7: Cryptographic Message Syntax; Version 1.5”), which has also been adopted in CMS (“Cryptographic Message. Syntax”, RFC 2630, IETF, June 1999). These standards are used, in particular, in the S/MIME (“Secure Multipurpose. Internet Mail Extensions”) specification for signed electronic mail. They are based on certificates issued by PKIX (X.509, CRL, OCSP) and are “extendable”, in the sense that it is possible to add extensions (supplementary information) which can be signed (authenticated/Attributes) or unsigned (unauthenticated/Attributes).        XML-DSig, belonging to the XML (“extended Markup Language”) family of data formats. This format enables certificates issued by PKIX to be used, and is also extendable.        PGP, corresponding to the signed messages produced by the PGP (“Pretty Good Privacy”) software marketed by Networks Associates Technology, Inc. and similar products. These certificates are different from those issued by PKIX.        
Clearly, with these electronic signature formats the signature certificate has to have a key usage which permits the signature. However, the key usage in question is not always the same, varying with the tools used. For example, the Netscape Mail messaging software produced by Netscape Communications Corporation and Outlook Express produced by Microsoft Corporation require different key usages. Furthermore, signing is not permitted if the certificate does not have one of these key usages.
There are services which enable a user to apply an electronic signature without himself having cryptographic equipment. Services of this kind can operate in various ways:                1/ The user is registered at a server which stores, in encrypted form, a locked signature key and a certificate in his name. When the user wishes to apply a signature, he sends the data to be signed to the server, together with a password for decrypting and unlocking his signature key. The server uses this password and these data to apply the signature, and returns the result to the user. A drawback of this mode of operation is that the user does not control his means of signature. Since the signatures are not applied at his station, he cannot be certain that the server will not apply other signatures without his knowledge.        2/ The user is registered at a server which stores, in encrypted form, a signature key and a certificate in his name. When the user wishes to apply a signature, he authenticates himself at the server, and the server sends him his encrypted signature key. The user decrypts his key by means of a password known only to him, uses this key to apply his signature, and then deletes the key from his station. A drawback of this mode of operation is the presence of signature keys in a database on the server. A malicious individual having access to the key database could attempt to attack these keys in order to decrypt them, and consequently use them for applying signatures without the knowledge of the keyholder.        
When an electronic signature is used to guard against repudiation, it is desirable for the signature to remain valid for a certain period. In general, the period of validity required for the signature (of the order of ten years at the present time) is considerably longer than the period of validity of a certificate (one year at the present time). Furthermore, it is generally desirable to have not only a signature but also the date (and possibly the time) of the signature.
There are several well-known methods for locating a signature in time (time-stamping) and for extending the period of validity of a signature beyond that of the signatory's certificate:                Non-consensual time-stamping: the signatory himself places the time-stamping data element in his document and signs this data element as an integral part of the document. This guarantees only the agreement of the signatory himself as to the time, and does not enable the validity of the signature to be extended. In another embodiment, the non-consensual time-stamping is applied by a server and kept with the signature.        Consensual time-stamping: the signatory and the addressee of the signed document agree on a time-stamp, which the signatory places in his document and which he signs at the same time. A variant consists in having the time-stamp initially signed by the addressee, and placing this signed time-stamp in the document. In both cases, the signature can be considered to be correctly located in time because of the degree of protection provided by the protocol. Again, however, the validity of the signature cannot be extended.        Secure time-stamping: when the document has been signed, the signatory makes use of a “time-stamping third party”. This is a reliable third party holding a key and a certificate with a long life, in other words one whose life covers the period of validity of the signature. The time-stamping third party sends him a time-stamping token which comprises the time-stamp and a unique reference to the signed document, the token itself being signed by the time-stamping third party with his long-life key. This token guarantees the instant of time-stamping of the document in a cryptographically secure way. This makes it possible, on the one hand, to determine the time of signature from the time of the token, and, on the other hand, to extend the validity of the signature by extending it to the period of validity of the time-stamping token. There is, in particular, an IETF standard on time-stamping, namely the TSP (RFC 3161, “Internet X.509 Public Key Infrastructure; Time-Stamp Protocol”, August 2001).        
A number of methods can be used to authenticate a user at a server:                The static password. This is a character string sent by the user to the server. The server can also know this password and compare the transmitted value directly with the known value. Otherwise, it can know the result of an operation performed on this password, and initially perform this operation on the transmitted value before making the comparison.        The questionnaire. A number of questions are put to the user, who is considered to be the only party who knows the answers, and who has previously answered the same questions to record the answers. The questions are generally of the following type: mother's maiden name, football team supported, favorite cartoon character, dog's name, etc.        The calculated password. The user has a device which performs a calculation, different on each occasion, on the basis of a secret key shared between the device and the server and a pseudo-random element such as the time. The server performs the same calculation and compares the results. If the values are identical, the user must be in possession of the device, and is therefore who he claims to be.        The non-reusable password. The user has a certain number of one-time codes, in the form of scratch cards for example, which are referenced at the server. If the code submitted for authentication is one of those that the user is considered to hold, the authentication is successful.        Challenge/response with secret key. The user shares a secret key with the server. The server sends a random number to the user (the “challenge”). The user performs a calculation on the challenge with the aid of the secret key and sends back the result of the calculation (the “response”). The server performs the same calculation and compares its result with the response sent by the user. If there is a match, the user is authenticated.        Challenge/response with public key. The user has a private key of which he is the sole holder. The server knows the public key corresponding to this private key, in the form of a certificate for example. The server sends a random challenge to the user, who performs a calculation on this challenge with the aid of his private key. The resulting response is sent to the server, which applies the reverse calculation to it with the aid of the public key. If this results in the original challenge sent, the user is authenticated.        
It should be noted that the availability of an authentication resource is not generally sufficient for the electronic signature of a document. In order to apply an electronic signature, a user must be the only party in possession of a secret, whereas in most authentication mechanisms (except the public key challenge/response system) the secret has to be shared in order to be verifiable by the server.
An object of the present invention is to propose a simple and efficient method enabling a user having authentication resources to apply an electronic signature.